
#include "Graph.hpp"
#include <string>
#include <cstring>

int main()
{
    // 邻接矩阵测试
    // matrix::Graph<char, int, INT32_MAX, false> it("abcd", 4);
    // it.addeage('a', 'b', 1);
    // it.addeage('a', 'c', 1);
    // it.addeage('a', 'd', 1);
    // it.addeage('b', 'a', 1);
    // it.addeage('b', 'c', 1);
    // it.addeage('b', 'd', 1);
    // it.showgrapth();

    // 邻接表测试
    // list::Graph<char, int, INT32_MAX> _list("abcd", 4);
    // _list.addeage('a', 'b', 1);
    // _list.addeage('a', 'c', 2);
    // _list.addeage('a', 'd', 3);

    // _list.showgrapth();

    //  遍历测试
    // string a[] = { "张三", "李四", "王五", "赵六","周六"};
    // matrix::Graph<string, int> g1(a, 5);
    // g1.addedge("张三", "李四", 100);
    // g1.addedge("张三", "王五", 200);
    // g1.addedge("王五", "赵六", 30);
    // g1.addedge("王五", "周六", 30);

    // g1.showgrapth();
    // g1.DFS("赵六");
    // g1.BFS("赵六");

    // // Kruskal算法  & Prim算法 测试用例
    //     const char* str = "abcdefghi";
    //     matrix::Graph<char, int> g(str, strlen(str));
    //     g.addedge('a', 'b', 4);
    //     g.addedge('a', 'h', 8);
    // // g.AddEdge('a', 'h', 9);
    //     g.addedge('b', 'c', 8);
    //     g.addedge('b', 'h', 11);
    //     g.addedge('c', 'i', 2);
    //     g.addedge('c', 'f', 4);
    //     g.addedge('c', 'd', 7);
    //     g.addedge('d', 'f', 14);
    //     g.addedge('d', 'e', 9);
    //     g.addedge('e', 'f', 10);
    //     g.addedge('f', 'g', 2);
    //     g.addedge('g', 'h', 1);
    //     g.addedge('g', 'i', 6);
    //     g.addedge('h', 'i', 7);

    //     matrix::Graph<char, int> kminTree(str, strlen(str));
    //     cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
    //     kminTree.showgrapth();

    //     cout << "------------------------" << endl;

    //     matrix::Graph<char, int> PminTree(str, strlen(str));
    //     cout << "Prim:" << g.Prim(PminTree, 'a') << endl;
    //     kminTree.showgrapth();

    // // Dijkstra 最短路径
    // const char *str = "syztx";
    // matrix::Graph<char, int, INT32_MAX, true> g(str, strlen(str));
    // g.addedge('s', 't', 10);
    // g.addedge('s', 'y', 5);
    // g.addedge('y', 't', 3);
    // g.addedge('y', 'x', 9);
    // g.addedge('y', 'z', 2);
    // g.addedge('z', 's', 7);
    // g.addedge('z', 'x', 6);
    // g.addedge('t', 'y', 2);
    // g.addedge('t', 'x', 1);
    // g.addedge('x', 'z', 4);

    // g.Dijkstra('s');

    // // 测试Bellman_Ford
    // const char *str = "abcdef";
    // matrix::Graph<char, int, INT32_MAX, true> g(str, strlen(str));
    // g.addedge('a', 'b', 10);
    // g.addedge('a', 'f', 3);
    // g.addedge('f', 'e', 1);
    // g.addedge('f', 'b', 2);
    // g.addedge('f', 'd', 6);
    // g.addedge('b', 'c', 7);
    // g.addedge('b', 'd', 5);
    // g.addedge('d', 'e', 7);
    // g.addedge('d', 'c', 4);
    // g.addedge('d', 'a', 3);

    // g.Dijkstra('a');
    // cout << "------------" << endl;
    // g.Bellman_Ford('a');

    // const char *str = "syztx";
    // matrix::Graph<char, int, INT32_MAX, true> g(str, strlen(str));
    // g.addedge('s', 't', 6);
    // g.addedge('s', 'y', 7);
    // g.addedge('y', 'z', 9);
    // g.addedge('y', 'x', -3);
    // g.addedge('z', 's', 2);
    // g.addedge('z', 'x', 7);
    // g.addedge('t', 'x', 5);
    // g.addedge('t', 'y', 8);
    // g.addedge('t', 'z', -4);

    // cout << "------------" << endl;
    // auto n = g.Bellman_Ford('s');
    // if (!n)
    //     cout << "存在负权回路" << endl;

    // // 微调图结构，带有负权回路的测试
    // const char *str = "syztx";
    // matrix::Graph<char, int, INT32_MAX, true> g(str, strlen(str));
    // g.addedge('s', 't', 6);
    // g.addedge('s', 'y', 7);
    // g.addedge('y', 'x', -3);
    // g.addedge('y', 'z', 9);
    // g.addedge('y', 'x', -3);
    // g.addedge('y', 's', 1); // 新增
    // g.addedge('z', 's', 2);
    // g.addedge('z', 'x', 7);
    // g.addedge('t', 'x', 5);
    // g.addedge('t', 'y', -8); // 更改
    // g.addedge('t', 'z', -4);
    // g.addedge('x', 't', -2);
    // vector<int> dist;
    // vector<int> parentPath;
    // if (g.Bellman_Ford('s'))
    // {
    //     g.Bellman_Ford('s');
    // }
    // else
    // {
    //     cout << "存在负权回路" << endl;
    // }

    // Floyd_warshall算法
    const char *str = "syztx";
    matrix::Graph<char, int, INT32_MAX, true> g(str, strlen(str));
    g.addedge('s', 't', 6);
    g.addedge('s', 'y', 7);
    g.addedge('y', 'z', 9);
    g.addedge('y', 'x', -3);
    g.addedge('z', 's', 2);
    g.addedge('z', 'x', 7);
    g.addedge('t', 'x', 5);
    g.addedge('t', 'y', 8);
    g.addedge('t', 'z', -4);

    cout << "------------" << endl;
    auto n = g.Floyd_warshall();

    //  const char *str = "abcdef";
    // matrix::Graph<char, int, INT32_MAX, true> g(str, strlen(str));
    // g.addedge('a', 'b', 10);
    // g.addedge('a', 'f', 3);
    // g.addedge('f', 'e', 1);
    // g.addedge('f', 'b', 2);
    // g.addedge('f', 'd', 6);
    // g.addedge('b', 'c', 7);
    // g.addedge('b', 'd', 5);
    // g.addedge('d', 'e', 7);
    // g.addedge('d', 'c', 4);
    // g.addedge('d', 'a', 3);

    // g.Floyd_warshall();

    return 0;
}
